Dynamic Bayesian Networks (DBNs) have been widely used in software applications for purposes of making dynamic decisions by electronically modeling decision processes. Some example applications that are particularly well suited for DBNs include speech recognition, visual tracking, pattern recognition, and the like.
DBN is based on Bayesian logic which is generally applied to automated decision making and inferential statistics that deals with probability inference.
A DBN application differs from a static Bayesian Network in that the DBN can adjust itself over time for stochastic (probabilistic) variables. Since most decisions evolve over time, DBN applications are typically favored over static Bayesian Network applications.
A Viterbi path is an optimal Most Probable Explanation (MPE) decision state sequence for a given sequence of observed outputs. In other words, if a result is known, the Viterbi path is a most likely path of the states for all hidden variables. The Viterbi path best explains a particular result. Once a DBN has been trained or used for a few different decisions, the DBN can be used to produce its own decision based on observable evidence for a given problem, or used to evaluate different observations. Thus, the DBN is particularly well suited for electronic applications that are difficult to program in order to capture all known possibilities, such as speech recognition, visual tracking, pattern recognition, and the like.
A number of conventional algorithms have been developed in order to generate a Viterbi path from a DBN. One popular algorithm was developed by Kevin P. Murphy (KPM algorithm). The KPM algorithm finds the Viterbi path by processing a forward loop (referred to as the “forward pass”) and backward loop (referred to as the “backward pass”) on the DBN. This technique is computationally expensive and utilizes excessive and unnecessary memory since during the backward pass all potential values (probabilities) of the junction trees (trees derived from the DBN) are needed to determine the Viterbi path. Moreover, because of memory requirements needed to save the potential values, if a complex DBN or long observation sequence is needed, then the KPM algorithm becomes incapable or impractical to use for generating the Viterbi path.
Therefore, there is a need for improved Viterbi path generation with DBNs.